/*
 * @lc app=leetcode.cn id=1482 lang=typescript
 *
 * [1482] 制作 m 束花所需的最少天数
 */

// @lc code=start

interface Check<T> {
  (bloomDay: T[], days: T, m: T, k: T): boolean;
}

function minDays(bloomDay: number[], m: number, k: number): number {
  const size = bloomDay.length;
  // 花朵数量不够制作花束
  if (m * k > size) return -1;
  // 检测当前天数days是否可以制作满足条件的花束
  const check: Check<number> = (bloomDay, days, m, k): boolean => {
    let flowers = 0;
    let bouquet = 0;
    const size = bloomDay.length;
    for (let i = 0; i < size; i++) {
      if (bloomDay[i] <= days) {
        flowers++;
        if (flowers === k) {
          bouquet++;
          flowers = 0;
        }
      } else {
        flowers = 0;
      }
    }
    return bouquet >= m;
  };

  let low = Math.min(...bloomDay);
  let high = Math.max(...bloomDay);
  // 二分查找可以制作花束的最小天数
  while (low < high) {
    const mid = low + ((high - low) >> 1);
    if (check(bloomDay, mid, m, k)) {
      high = mid;
    } else {
      low = mid + 1;
    }
  }

  return low;
}
// @lc code=end
